Run-length encoding is an encoding scheme used when compressing image and music signals. For example, image encoding schemes such as JPEG (Joint Photographic Experts Group), MPEG-2 (Moving Picture Experts Group Phase-2), MPEG-4 (Moving Picture Experts Group Phase-4), H.264, and so forth, use run-length encoding.
The run-length encoding is applied to compression of signals in which zero appears frequently. The run-length encoding encodes the number of zeros appearing before a non-zero signal and the value of the non-zero signal, as one set of information.
Run-length encoding will now be described, taking as an example an encoding scheme for a 4×4 block in a video encoding scheme H.264. FIGS. 5A to 5C are diagrams respectively illustrating an encoding procedure for the 4×4 block in the H.264. In FIG. 5A, the 4×4 block shows coefficients after a DCT (Discrete Cosine Transform). As shown in FIG. 5B, a zigzag scan is performed on the coefficients of the 4×4 block, to rearrange the coefficients as shown in FIG. 5C.
Non-zero coefficients and zero coefficients are found from among the rearranged coefficients, and information such as    (1) the number of zeros before each non-zero coefficient,    (2) the value of each non-zero coefficient, and    (3) the number of non-zero coefficients is extracted.
In order to efficiently extract the abovementioned information, (1), (2), and (3), positions of the non-zero coefficients should be found.
The positions of the non-zeros are indexes representing order of coefficients on which zigzag scanning and arranging has been performed. The index of a first coefficient is 0, the index of a subsequent coefficient is 1, the index of a next subsequent coefficient is 2, and so on.
When the indexes of the non-zero coefficients are known, it is possible to compute the number of non-zero coefficients, and the number of zeros before the non-zero coefficients.
However, processors such as conventional CPUs (Central Processing Units), DSPs (Digital Signal Processors), or the like, cannot obtain the indexes of the non-zero coefficients at high speed. Conventional CPUs and DSPs are said to be rather unsuitable for high speed processing of run-length encoding.
On processors such as CPUs, DSPs, or the like, indexes of the non-zero coefficients are normally found by scanning the coefficients in order. If the coefficients are scanned in order, time and effort are required according to the number of coefficients. As a result, the conventional processors cannot efficiently find indexes of the non-zero coefficients.
The run-length encoding, which requires a process of counting the number of zeros, is sequential processing. As a result, carrying out the run-length encoding in parallel is generally difficult.
If the process of counting the number of zeros can be performed in parallel, it is possible to speed up the run-length encoding on a processor to a greater extent than on conventional processors.
A method of performing the process of counting the number of zeros in parallel is disclosed in Patent Document 1. In the method disclosed in Patent Document 1, a signal is represented by a 1-bit flag as to whether a value is zero or not, and using a plurality of flags as one key, a run length is obtained from a run-length table. That is, the run-length table is used in order to obtain the run length. According to Patent Document 1, information of 256 elements is stored in the run-length table.
Obtaining the run length by the method of Patent Document 1 enables the obtaining of the run length with fewer steps than by obtaining the run length while scanning the signal in order.
Patent Document 2 discloses an encoding apparatus and method tor executing the run-length encoding. The run-length encoding apparatus of Patent Document 2 obtains the run length in the procedure of:    (a) a zero judgment of an input signal, and    (b) a run length computation.A process of (a) decides whether or not zero is present for all input signals, and stores a decision result thereof. Then, based on this decision result, the number of zeros present before a non-zero signal, is computed.[Patent Document 1]
JP Patent Kokai Publication No. JP-P2003-330911A
[Patent Document 2]
JP Patent Kokai Publication No. JP-P2004-166083A